maximum and minimum in an array
Problem: To find the maximum and minimum values among the elements in a given array.
Input: Given a one-dimensional array A of size n, where A contains n elements.
Output: The maximum and minimum of the n values.
Video Lecture
Finding Maximum and Minimum Example
Linear Approach Algorithm
FindingMaxMin(A[0]..A[n-1])
Input: Array A containing n elements.
Output: Maximum and Minimum of the n numbers.
Step 1: Start.
Step 2: Input array A.
Step 3: Initially, assign the first element of the array as both Max and Min: Max = Min = A[0].
Step 4: For i = 1 to n-1, do the following:
Step 5: If A[i] < Min, then set Min = A[i].
Step 6: If A[i] > Max, then set Max = A[i].
Step 7: Return Max and Min.
Step 8: Stop.
Divide and Conquer Approach
FindingMaxMin(A[0]..A[n-1])
Input: Array A containing n elements.
Output: Maximum and Minimum of the n numbers.
Step 1: Start.
Step 2: Divide the given array recursively into two parts until we have a single element. This is a recursive algorithm.
Step 3: Find the maximum value and minimum value of the left sub-array recursively.
Step 4: Find the maximum value and minimum value of the right sub-array recursively.
Step 5: Compare the results of Step 3 and Step 4 (i.e., the left sub-array and right sub-array). Find the maximum and minimum of the combined array.
Step 6: Return the maximum value and minimum value.
Step 7: Stop.
maximum and minimum in an array code
#include <stdio.h>
int main() {
int arr[] = {3, 5, 1, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
if (arr[i] < minVal) {
minVal = arr[i];
}
}
printf("Maximum: %d\n", maxVal);
printf("Minimum: %d\n", minVal);
return 0;
}
#include <iostream>
using namespace std;
int main() {
int arr[] = {3, 5, 1, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
if (arr[i] < minVal) {
minVal = arr[i];
}
}
cout << "Maximum: " << maxVal << endl;
cout << "Minimum: " << minVal << endl;
return 0;
}
public class Main {
public static void main(String[] args) {
int[] arr = {3, 5, 1, 8, 2};
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
if (arr[i] < minVal) {
minVal = arr[i];
}
}
System.out.println("Maximum: " + maxVal);
System.out.println("Minimum: " + minVal);
}
}
arr = [3, 5, 1, 8, 2]
max_val = arr[0]
min_val = arr[0]
for num in arr[1:]:
if num > max_val:
max_val = num
if num < min_val:
min_val = num
print("Maximum:", max_val)
print("Minimum:", min_val)
Analysis of Largest Sub-array Sum
Time Complexity
Basic Operation: Comparison
Analysis
There are n-1 iterations. Initially, the array's first element A[0] is assigned as both the minimum and maximum. The loop variable ranges from 1 to n-1. For every iteration, there are 2 comparisons: one for the maximum value and one for the minimum value. The comparison operation is performed n times. To find the maximum and minimum using a linear approach, the algorithm performs:
T(n) = 2 * (n-1) = O(n)
